This article is intended for the people who know shit about encryption and want a little more info about it. Hope it is useful.
Contents:
1) What is Encryption?
2) How does Encryption work?
3) Brute Force Attack
4) Factoring Techniques
5) How Long Should a Key be?
6) Mounting an Attack
7) What is RSA?
8) What is DES?
9) What us Substitution?
10) What is Permutation?
1) What is Encryption?
Encryption is simply the encoding of messages so that they cannot be read by anyone who does not know how to decipher it. Governments and militaries have been using codes to make their messages unreadable for many years. For example, Caesar used a code to send military messages that was simply a shift of the letters in the message three spaces down in the alphabet (an A becomes
a D). In cryptographic language this is known as a shift cypher.
The properties of a good cryptosystem are analogous to that of a normal lock. A good system will have a very large key which is one of a large number of keys (termed keyspace). It will also provide cyphertext (encrypted plaintext) that appears random and stands up to known decryption attacks. Lastly, the system should be suitable to the function for which it is intended. For example, if a message is to remain secret for ten years or more, then the system should take into account the future speed of computers and their
corresponding ability to attack the system. However, except for classified government information (and maybe the Coca-Cola secret recipe), the reality is that the relevance of most corporate information traveling over networks is measured in days or weeks, and not decades.
2) How Does Encryption Work?
Most encryption algorithms are based on the concept of complex mathematics that work in only one direction and are generally based on the difficulty of factoring very large numbers (keys) that are used for the encryption. These large numbers are the product of large prime numbers. For example, anyone can multiply two large prime numbers to obtain a result, but it is very difficult for someone else to factor the large number to get back the two primes. This is to say that mathematicians have yet to figure out a method for reversing the math effectively. In this way, cryptography has been a secure method of ensuring data confidentiality over computer networks.
3) Brute Force Attack
The traditional method of breaking complex mathematical codes is through brute-force attacks. This method is mathematically the easiest to perform, but relies on vast computer processing power and is therefore the easiest to defend against. A brute force attack tries every possible combination of keys in order to unlock the encryption. Therefore, simply increasing the keyspace will increase the amount of time needed to mount a brute force attack. The
reality is that a brute force attack is not a method which will ever be used to decode cyphertext. Some quick calculations relating computer speeds and key length will yield code-breaking times that exceed the expected life of the universe.
The brute force method needs a sample of unencrypted text for the computer to compare each decryption attempt with the actual text. This can be easily obtained by knowing the nature of the messages being intercepted. For example, all Microsoft word files will have a set of standard information (bytes). How the decryption functions is easy. A key that is 128 bits long will have 2128 possible values. Therefore, assuming that a very fast computer that can try one million keys per second (consider that attempting a key requires many instructions) it will take 225 years to try all of the
combinations with a 50% probability that it will be found in the first 224 years (remember that the universe is estimated to be 210 years old). (Bruce Schneier, Applied Cryptography c.1995).
4) Factoring Techniques
The more feasible form of attack will come from mathematicians refining existing and developing new factoring techniques. These methods have been used to show potential vulnerabilities in key-based encryption. However, they still require massive computer power and long time-frames to break the encryption. For example, a 129-digit number was factored at Bellcore labs in 1994. This used the idle time on 1600 computers around the world, over a period of 8 months using a computation called the quadratic sieve. The authors estimated that they used .03% of the computing power of the Internet, and believed that, with a highly publicized event, they could acquire 100,000 computers (approx. 2% of the Internet) without resorting to illegal or unethical efforts such as an Internet worm.
5) How Long Should a Key be?
The security of a cryptosystem depends on the strength of the algorithm and the length of the key. The strength of the algorithm is difficult to understand. However, understanding the methods of how the keys are decrypted provides some clues as to it's strength. Knowing that all numbers can be represented by a set of primes, encryption techniques rely on the difficulty of factoring very large numbers into their respective primes. Lets look at a very simplified example (cryptologists will undoubtedly cringe at the over simplification):
Suppose we have number n represented by x and y such that n = xy. The quadratic sieve method works by first assuming that the numbers x and y are close to one another on a number line. Successive steps either prove or disprove this and search out the next numbers. Therefore, effective encryption will create keys which are not close to one another. However, the numbers cannot be so far apart as to have the one of x or y set to a very small value. Effective encryption-based key generation will generate the keys
randomly, but also discard those keys which will be susceptible to
factor-based decryption systems.
What is involved in factoring a number? Anyone with a grade six education (or a calculator) can easily multiply together two numbers. Anyone with a grade 9 education (and who remembers it) can factor a small number into its primes. A prime number is any integer which is only divisible by itself and by 1. For
example, the sequence of the first seven prime numbers is: 1,2,3,5,7,11,13...
Lets say we express the number 24 as a set of its primes. This is simply 2*2*2*3 = 24. Seems simple enough. Now, for those of you who think this is easy, try entering the RSA factoring challenge and they will award you a prize if you can do it on very large numbers (see the link at the end of this document).
Another method called the general number field sieve can factor numbers approximately 10 times faster than the quadratic field sieve, but is only faster for larger numbers (greater than 110 digits). This method hasn't been refined to the degree of the quadratic sieve but, with time will likely be the method of choice for factoring large keys.
Factoring large numbers is very hard, but is becoming easier therefore predictions based on security required for long term encryption cannot be made. However, most people don't require their data to remain secure for 100 years. For example, information about stock market conditions may only be relevant for a few days. Decisions based on that information need only be protected for a few hours. At the end of the day everyone's trades become known anyway. For a manufacturer, design specs. need only be kept secret
until product launch. For the longest-term secrets, such as military secrets, key length should be based on the computing speeds at that time and the projected future increases. Two general rules of thumb is that computing power increases by a factor of 10 every five years and it is always best to be cautious when making predictions.
6) Mounting an Attack
With respect to computing methods, a hardware or a software based attack can be mounted. Hardware designers and cryptologists have designed machines specifically for breaking codes which can greatly increase the rate at which a code is broken. This involves hundreds of parallel processors working on different 'parts' of the key.
A software-based attack is much slower but is also much cheaper to mount. For example, using an algorithm with a 56 bit key, a software attempt run on 512 workstations capable of running the algorithm at a rate of 15,000 encryptions per second, running 24 hours per day would require 545 years to test all possible numbers (Bruce Schneier, Applied Cryptography c.1995) . Importantly,
with a 40 bit key (the only key length currently allowed for export under federal legislation) a similar network would take just under two days to complete the attack.
A 128 key makes brute force cryptanalysis effectively useless, even when factoring estimates for increases in the number of networked computers in the world and increasing processor speed. However, it is still susceptible to factoring methods when distributed among several computers. The next logical question is, why not use keys with a very large number of bits (>2000)? The answer lies in the tradeoff between security and usability. The longer the key length the longer the time needed for encryption. Encryption over a LAN
environment should not be a bottleneck in the communications.
7) What is RSA?
RSA is the industry standard for public key cryptography. Its algorithm is based on the difficulty of factoring large numbers. Encryption is performed 'one-way', indicating that f(x) is the encryption function but f-1(x) is very hard to compute.
8) What is DES?
Data Encryption Standard (DES) is the standard for private key encryption and is recognized by international standards organizations such as ANSI and ISO. Standard encryption schemes are needed to ensure interoperability of systems for the same reasons standards are needed for all network applications. The
most important criteria for a standard (and in fact any) cryptographic scheme is that the security must rely on the key and not in the secrecy of the algorithm. By the definition of encryption, simply deducing the algorithm should not make it any easier to decrypt messages.
DES uses the same key for encrypting as decrypting. This encryption is not based on the difficulty of factoring large numbers but is based on a set of non-linear transformations. The key can be any 56-bit number and there are few weak keys. A good example of a weak key is one that is all 0's or 1's. This encryption is not based on the difficulty of factoring large numbers but is based on a set of non-linear transformations. DES is a single combination
of operations, substitution followed by permutation, performed on the message based on the key and on a set of constant values (the algorithm). This function is repetitive and so can be easily implemented using hardware, making it a very fast solution for encryption.
9) What is a Substitution?
A substitution is quite easy to understand. Letters of the alphabet can be randomly substituted for other letters according to a key as follows:
a b c d e f g...
q s l b z e r...
This substitution key is held by both the person coding the message and the person decoding the message. The key is simply the substitution of the number of letters in the alphabet (and could include the space-value). Therefore the number of permutations is simply 26!. A very large number which could not be analyzed by brute force. However, this simple type of encryption can easily
be analyzed using other methods.
10) What is a Permutation?
A permutation does not involve changing the values of the plaintext. A permutation alters their position but leaves the character values unchanged. The method is performed mathematically using a permutation matrix in which each row contains only one '1' for the row of size 'm'. The best way to
illustrate this is through a simple alphabetic example:
We will use the following key (m=4)Value: 1 2 3 4 Key: 3 4 1 2 to encrypt the following: howareyou.
First arrange in groups: howa|reyo|u
Perform the permutation: wahoyoreu
Decrypt with the inverse key.
DES functions by first dividing the initial text (bitstring) of length 64 bits, into two halves (32 bits). The 32 bit string is expanded to 48 bits. An initial permutation is performed on the bitstring according to a function derived from the encryption key. The DES algorithm then performs a set of constant substitution functions using 8 S-boxes followed by the permutation (An S-box is the term for a 4x16 matrix which is used to perform the substitution on the bitstring of length, 48 bits). This is followed by a round of key-based encryption using 48 of the 56 bits in the key. The whole set of functions is repeated 16 times.
